package com.wss.lsl.test.driven.arithmetic;

/**
 * 寻找最大子数组。递归解法
 * 
 * @author weiss
 *
 */
public class FindMaxImumSubArray {

	public static int[] findMaxImumSubArray(int[] data, int low, int high) {
		if (low == high) {// 基本情况
			return new int[] { low, high, data[low] };
		}

		// 递归情况
		int mid = (low + high) / 2;
		int[] leftArraySum = findMaxImumSubArray(data, low, mid); // 左子数组
		int[] rightArraySum = findMaxImumSubArray(data, mid + 1, high); // 右子数组
		int[] crossArraySum = finadMaxCrossSubArray(data, low, mid, high); // 跨过中点的子数组

		int leftSum = leftArraySum[2];
		int rightSum = rightArraySum[2];
		int crossSum = crossArraySum[2];
		if (leftSum >= rightSum && leftSum >= crossSum) {// 左子数组最大
			return leftArraySum;
		} else if (rightSum >= leftSum && rightSum >= crossSum) { // 右子数组最大
			return rightArraySum;
		} else {// 跨域中点的子数组最大
			return crossArraySum;
		}
	}

	/**
	 * 跨域中点的子数组最大
	 * 
	 * @return
	 */
	private static int[] finadMaxCrossSubArray(int[] data, int low, int mid, int high) {

		int leftSum = data[mid];
		int sum = leftSum;
		int maxLeft = mid;

		for (int i = maxLeft - 1; i >= low; i--) {
			sum += data[i];
			if (sum > leftSum) {
				leftSum = sum;
				maxLeft = i;
			}
		}

		int rightSum = data[mid + 1];
		sum = rightSum;
		int maxRight = mid + 1;
		for (int j = maxRight + 1; j <= high; j++) {
			sum += data[j];
			if (sum > rightSum) {
				rightSum = sum;
				maxRight = j;
			}
		}

		return new int[] { maxLeft, maxRight, leftSum + rightSum };
	}
}
